
package Graph;




/**
 * @author SASHA
 *
 */

public class optimalWay{
	public static int length_matrix [][];
	private int graph [][];
	private float jams [][];
	private int number;
	int maxVertexes;
	public int carsOnRoads [][];
	
	public optimalWay(Graph City){
		jams = City.getJams();
		carsOnRoads = City.getCarsOnRoads();
		maxVertexes = City.getmaxVertexes();
		length_matrix = new int [maxVertexes][maxVertexes];
		graph = new int [maxVertexes][maxVertexes];
		graph = City.getGraph();
		number = City.getNumber();
		int i, j, k;
		for (i = 0; i < Graph.maxVertexes; i++){
			for (j = 0; j < Graph.maxVertexes; j++){
				length_matrix[i][j] = graph[i][j];
			}
		}
		for(k = 0; k < number; k++){
			for (i = 0; i < number; i++){
				for (j = 0; j < number; j++){
					length_matrix[i][j] = min(length_matrix[i][j], length_matrix[i][k] + length_matrix[k][j]);
				}
			}
		}
	}
	
	public void refresh(Graph City){
		graph = City.getGraph();
		number = City.getNumber();
		int i, j, k;
		for (i = 0; i < maxVertexes; i++){
			for (j = 0; j < maxVertexes; j++){
				if(carsOnRoads [i][j] >= 20) jams[i][j] = 6;
				else jams[i][j] = (float) carsOnRoads[i][j] / 4 + 1f;
				length_matrix[i][j] = ((graph[i][j]) * (int) (jams [i][j]));
			}
		}
		for(k = 0; k < number; k++){
			for (i = 0; i < number; i++){
				for (j = 0; j < number; j++){
					length_matrix[i][j] = min(length_matrix[i][j], length_matrix[i][k] + length_matrix[k][j]);
				}
			}
		}
	}
	
	
	public static int min (int a, int b){
		if (a <= b) return a;
		else return b;
	}
	
	
	
	public int setCourse(Graph City, pathway oWay, int startNum, int finalNum, int flag){
		int i;
		int optimalLength;
		
		if(length_matrix[startNum][finalNum] >= City.getNoRoad()){
			System.out.print("Vertex #" + startNum + " cannot be reached from vertex #" + finalNum + "!!!\n");
			oWay.addVertex(startNum);
		}
		if (flag == 0){
			oWay.setLength(0);
			oWay.addVertex(startNum);
			optimalLength = length_matrix[startNum][finalNum];
		} else optimalLength = flag;
		
		for (i = 0; i < number; i++){
			if(graph[startNum][i] >= Graph.no_road) continue;
			if(i == startNum) continue;
			if(i == finalNum){
				oWay.addVertex(i);
				break;
			}
			if(optimalLength == graph[startNum][i] + length_matrix[i][finalNum]){
				oWay.addVertex(i);
				if(optimalLength - length_matrix[startNum][i] < 0) {
					System.out.print("SHIT!!!\n");
					return -1;
				}
				setCourse (City, oWay, i, finalNum, (optimalLength - length_matrix[startNum][i]));
				break;
			}
		}
		return 1;
	}
	
	public pathway getCourse(Graph City, int startNum, int finalNum){
		pathway Way = new pathway();
		while(setCourse(City, Way, startNum, finalNum, 0) < 0);
		return Way;
	}
}
